package com.sise.Linked;

/**
 *      203. 移除链表元素
 *
 *      给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
 */
public class _203_removeElements {


    /**
     * 方法一：正常迭代
     */
    public ListNode removeElements(ListNode head, int val) {

        // 由于可能删除的是 第一个节点，故此设置一个 虚拟头结点
        ListNode dummyNode = new ListNode(val - 1);
        dummyNode.next = head;
        ListNode prev = dummyNode;

        // 这里用的是 prev.next，方便后续跳过 val 节点
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }

        return dummyNode.next;
    }

    /**
     * 方法二：递归。递归返回可用的 头结点 head
     */
    public ListNode removeElements_2(ListNode head, int val) {
        if (head == null) return null;
        head.next = removeElements_2(head.next, val);
        // 如果当前数值和 val 相等，那么就返回自己的后一个值，等于跳过当前值。
        if (head.val == val) {
            return head.next;
        } else {
            return head;
        }
    }
}
